#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "includes/common.h"
#include "includes/mybtree.h"

// 磁盘相关
static int mybtree_disk_write(void *d, int off, int len, char *name);
static int mybtree_disk_read(void *d, int off, int len, char *name);
static void mybtree_disk_flush_handler(mybtree *t, mybnode *n, int);

mybnode *mybtree_child_get(mybtree *t, mybnode *n, int idx);
void *mybtree_data_get(mybtree *t, mybnode *n, int idx);
static void *mybtree_do_find(mybtree *t, mybnode *n, int key);
static mybnode *mybtree_node_create(mybtree *t, int leaf, int idx);
static void mybtree_node_release(mybtree *t, mybnode *n);
static void mybtree_child_split(mybtree *t, mybnode *n, int child_idx);
static void mybtree_child_merge(mybtree *t, mybnode *n, int child_idx);
static int mybtree_child_take(mybtree *t, mybnode *n, int child_idx);
static void mybtree_insert_nofull(mybtree *t, mybnode *n, int key, void *data);
static void mybtree_do_delete(mybtree *t, mybnode *n, int key, int idx);

mybtree *mybtree_create(char *name) {
    mybtree *t = (mybtree *) calloc(sizeof(mybtree), 1);
    int len = mybtree_disk_read(t, 0, sizeof(mybtree), str_concat(name, MYBTREE_DISK_INDEX_FILE_SUFFIX));
    t->name = name;
    t->bitmap_idx.data = t->bitmap_idx_data;
    t->bitmap_idx.size = MYBTREE_BITMAP_SIZE;
    t->bitmap_data.data = t->bitmap_data_data;
    t->bitmap_data.size = MYBTREE_BITMAP_SIZE;
    mybitmap_set(&t->bitmap_idx, 0); // 存放mybtree结构体
    mybitmap_set(&t->bitmap_data, 0); // 存放mybtree结构体
    if(!len) {
        t->root_idx = 1;
        t->keys_num = 0;
        t->nodes_num = 1;
        t->threthod = MYBTREE_KEYS_THRETHOD;
        t->node_size = MYBTREE_DISK_NODE_SIZE;
        mybitmap_set(&t->bitmap_idx, 1); // 存放root节点
    }

    mybnode *root = mybtree_node_create(t, 1, t->root_idx);
    if(len) {
        mybtree_disk_read(root, MYBTREE_DISK_OFFSET(t->root_idx), MYBTREE_DISK_NODE_SIZE, str_concat(name, MYBTREE_DISK_INDEX_FILE_SUFFIX));
        if(root->leaf) {
        for (int i = 0; i < MYBTREE_KEYS_NUM_MAX; i++)
            {
                root->datas[i] = 0;
            }
        } else {
            for (int i = 0; i < MYBTREE_CHILDS_NUM_MAX; i++)
            {
                root->childrens[i] = 0;
            }
        }
    }
    t->root = root;
    // printf("read data success, root_idx: %d, leaf: %d, keys: %d, bitmap: %b\n", t->root_idx, root->leaf, root->keys_num, t->bitmap_idx.data[0]);
    return t;
}

void *mybtree_find(mybtree *t, int key) {
    return mybtree_do_find(t, t->root, key);
}

void mybtree_insert(mybtree *t, int key, void *data) {
    mybnode *r = t->root;
    // printf("start mybtree_insert root: %x\n", r);
    if(MYBTREE_NODE_IS_FULL(r)) {
        printf("when root is full root data: %d, %d, %d\n", *(int *)r->datas[0], *(int *)r->datas[1], *(int *)r->datas[2]);
        mybnode *n = mybtree_node_create(t, 0, 0);
        t->root = n;
        t->root_idx = n->node_idx;
        t->nodes_num++;
        n->childrens[0] = r;
        n->children_idxs[0] = r->node_idx;
        mybtree_child_split(t, t->root, 0);
        printf("after split, root: %p(%d), leaf: %d, key: %d, len: %d, child1: %p, child2: %p\n", t->root, t->root->node_idx, t->root->leaf, t->root->keys[0], t->root->keys_num, t->root->childrens[0], t->root->childrens[1]);
    }
    mybtree_insert_nofull(t, t->root, key, data);
}

void mybtree_delete(mybtree *t, int key) {
    mybtree_do_delete(t, t->root, key, -1);
}

static void mybtree_do_delete(mybtree *t, mybnode *n, int key, int idx) {
    int i = 0;
    if(idx >= 0) {
        i = idx;
    } else {
        while (i < n->keys_num && key > n->keys[i]) i++;
    }
    if((idx >= 0 || (i < n->keys_num && key == n->keys[i])) && n->leaf) {
        // 找到key
        arr_move_left_byte(n->keys, i + 1, n->keys_num - i - 1, 1, sizeof(int));
        arr_move_left_byte(n->data_idxs, i + 1, n->keys_num - i - 1, 1, sizeof(int));
        arr_move_left_byte(n->datas, i + 1, n->keys_num - i - 1, 1, sizeof(int));
        n->keys_num--;
        t->keys_num--;
        mybitmap_clear(&t->bitmap_data, n->data_idxs[i]);
    } else if(!n->leaf)  {
        mybnode *c = mybtree_child_get(t, n, i);
        int need_merge = mybtree_child_take(t, n, i);
        if(need_merge) mybtree_child_merge(t, n, i);
        mybtree_do_delete(t, c, key, -1);
    }
}

static void *mybtree_do_find(mybtree *t, mybnode *n, int key) {
    int i = 0;
    while (i < n->keys_num && key > n->keys[i])
    {
        i++;
    }
    if(i < n->keys_num && key == n->keys[i] && n->leaf) {
        void *data = mybtree_data_get(t, n, i);
        // printf("find key: %d, node: %d, idx: %d, data: %d\n", key, n->node_idx, i, *(int *)data);
        return data;
    }
    if(n->leaf) return NULL;
    n = mybtree_child_get(t, n, i);
    if(n) mybtree_do_find(t, n, key);
    else return NULL;
}

static int mybtree_disk_write(void *d, int off, int len, char *fname) {
    int wlen = len;
    if(len > MYBTREE_DISK_NODE_SIZE) wlen = MYBTREE_DISK_NODE_SIZE;
    FILE *fd = fopen(fname, "a+");
    fclose(fd);
    fd = fopen(fname, "r+");
    fseek(fd, off, SEEK_SET);
    int res = fwrite(d, 1, wlen, fd);
    // printf("after fwrite,fd: %x, off: %d, wlen: %d, res: %d\n", fd, off, wlen, res);
    fclose(fd);
    free(fname);
    return res;
}

static int mybtree_disk_read(void *d, int off, int len, char *fname) {
    int rlen = len;
    if(len > MYBTREE_DISK_NODE_SIZE) rlen = MYBTREE_DISK_NODE_SIZE;
    FILE *fd = fopen(fname, "r");
    // printf("after fopen fd: %x, off: %d, rlen: %d, len: %d\n", fd, off, rlen, len);
    if(!fd) return 0;
    fseek(fd, off, SEEK_SET);
    int res = fread(d, 1, rlen, fd);
    // printf("after fread file: %s, rlen: %d, off: %d, res: %d\n", fname, rlen, off, res);
    fclose(fd);
    free(fname);
    return res;
}

mybnode *mybtree_child_get(mybtree *t, mybnode *n, int idx) {
    // if(idx < 10) printf("do read child idx: %d\n", n->children_idxs[idx]);
    if(n->childrens[idx]) {
        return n->childrens[idx];
    } else if(n->children_idxs[idx]) {
        mybnode *c = mybtree_node_create(t, 0, n->children_idxs[idx]);
        mybtree_disk_read(c, MYBTREE_DISK_OFFSET(n->children_idxs[idx]), MYBTREE_DISK_NODE_SIZE, str_concat(t->name, MYBTREE_DISK_INDEX_FILE_SUFFIX));
        n->childrens[idx] = c;
        if(c->leaf) {
            for (int i = 0; i < MYBTREE_KEYS_NUM_MAX; i++)
            {
                c->datas[i] = 0;
            }
        } else {
            for (int i = 0; i < MYBTREE_CHILDS_NUM_MAX; i++)
            {
                c->childrens[i] = 0;
            }
        }
        return c;
    }
    return NULL;
}

void *mybtree_data_get(mybtree *t, mybnode *n, int idx) {
    if(n->datas[idx]) {
        return n->datas[idx];
    } else if(n->data_idxs[idx]) {
        void *res = (void *)calloc(1, MYBTREE_DISK_RECORD_SIZE);
        mybtree_disk_read(res, MYBTREE_DISK_DATA_OFFSET(n->data_idxs[idx]), MYBTREE_DISK_RECORD_SIZE, str_concat(t->name, MYBTREE_DISK_DATA_FILE_SUFFIX));
        // printf("[mybtree_data_get] idx: %d, disk idx: %d, data: %d\n", idx, n->data_idxs[idx], *(int *)res);
        n->datas[idx] = res;
        return res;
    }
    return NULL;
}

int mybtree_flush_disk(mybtree *t) {
    mybtree_disk_write(t, 0, MYBTREE_DISK_NODE_SIZE, str_concat(t->name, MYBTREE_DISK_INDEX_FILE_SUFFIX));
    int idx = 0;
    mybtree_travel(t, t->root, mybtree_disk_flush_handler, &idx);
}

void mybtree_travel(mybtree *t, mybnode *n, mybtree_travel_handler hander, int *idx) {
    if(n == NULL) return;
    hander(t, n, (*idx)++);
    if(!n->leaf) {
        int i = 0;
        mybnode *c;
        while((c = mybtree_child_get(t, n, i++))) {
            mybtree_travel(t, c, hander, idx);
        }
    }
}

static void mybtree_disk_flush_handler(mybtree *t, mybnode *n, int idx) {
    // printf("[mybtree_disk_flush_handler] write node idx: %d, leaf: %d, offset: %x\n", n->node_idx, n->leaf, MYBTREE_DISK_OFFSET(n->node_idx));
    mybtree_disk_write(n, MYBTREE_DISK_OFFSET(n->node_idx), MYBTREE_DISK_NODE_SIZE, str_concat(t->name, MYBTREE_DISK_INDEX_FILE_SUFFIX));
    if(n->leaf) {
        int i = 0;
        while(n->datas[i] && n->data_idxs[i])
        {
            // printf("[mybtree_disk_flush_handler] write data, data idx: %d, data: %d\n", n->data_idxs[i], *(int *)n->datas[i]);
            mybtree_disk_write(n->datas[i], MYBTREE_DISK_DATA_OFFSET(n->data_idxs[i]), MYBTREE_DISK_RECORD_SIZE, str_concat(t->name, MYBTREE_DISK_DATA_FILE_SUFFIX));
            i++;
        }
        
    }
}

static mybnode *mybtree_node_create(mybtree *t, int leaf, int idx) {
    mybnode *n = (mybnode *) calloc(1, sizeof(mybnode));
    n->leaf = leaf;
    n->keys_num = 0;
    n->node_idx = idx ? idx : mybitmap_allocate(&t->bitmap_idx);
    return n;
}

static void mybtree_node_release(mybtree *t, mybnode *n) {
    mybitmap_clear(&t->bitmap_idx, n->node_idx);
    t->nodes_num--;
    free(n);
}

static void mybtree_child_split(mybtree *t, mybnode *n, int child_idx) {
    mybnode *c = mybtree_child_get(t, n, child_idx);
    // if(c->leaf) {
    //     printf("before child split, node: %d, data: %d, %d, %d\n", n->children_idxs[child_idx], *(int *)c->datas[0], *(int *)c->datas[1], *(int *)c->datas[2]);
    // }
    mybnode *c_right = mybtree_node_create(t, c->leaf, 0);
    // 分t - 1给c_right
    memcpy(c_right->keys, c->keys + MYBTREE_KEYS_THRETHOD, MYBTREE_KEYS_NUM_MIN);
    memcpy(c_right->data_idxs, c->data_idxs + MYBTREE_KEYS_THRETHOD, MYBTREE_KEYS_NUM_MIN);
    memcpy(c_right->datas, c->datas + MYBTREE_KEYS_THRETHOD, MYBTREE_KEYS_NUM_MIN);
    if(!c->leaf) {
        c_right->children_idxs[MYBTREE_CHILDS_NUM_MIN - 1] = c->children_idxs[MYBTREE_CHILDS_NUM_MAX - 1];
        c_right->childrens[MYBTREE_CHILDS_NUM_MIN - 1] = c->childrens[MYBTREE_CHILDS_NUM_MAX - 1];
        c->keys_num = MYBTREE_KEYS_THRETHOD - 1;
    } else {
        c->keys_num = MYBTREE_KEYS_NUM_MIN + 1; // 叶节点保留中间元素
        uint32_t tmp_idx = c->right_idx;
        mybnode *tmp = c->right;
        c->right_idx = c_right->node_idx;
        c->right = c_right;
        c_right->left_idx = c->node_idx;
        c_right->left = c;
        c_right->right_idx = tmp_idx;
        c_right->right = tmp;
    }
    c_right->keys_num = MYBTREE_KEYS_NUM_MIN;
    // 中间key上升
    arr_move_right_byte(n->keys, child_idx, n->keys_num - child_idx, 1, sizeof(int));
    arr_move_right_byte(n->children_idxs, child_idx + 1, n->keys_num - child_idx, 1, sizeof(int));
    arr_move_right_byte(n->childrens, child_idx + 1, n->keys_num - child_idx, 1, sizeof(int));
    n->keys[child_idx] = c->keys[MYBTREE_KEYS_NUM_MIN];
    n->children_idxs[child_idx + 1] = c_right->node_idx;
    n->childrens[child_idx + 1] = c_right;
    n->keys_num++;
    t->nodes_num++;
    // if(c->leaf) {
    //     printf("after child split, data: %d, %d, %d\n", *(int *)c->datas[0], *(int *)c->datas[1], *(int *)c->datas[2]);
    // }
}

// 子节点child_idx与child_idx+1合并
static void mybtree_child_merge(mybtree *t, mybnode *n, int child_idx) {
    mybnode *c = mybtree_child_get(t, n, child_idx);
    mybnode *br = mybtree_child_get(t, n, child_idx + 1);
    if(!br) {
        mybnode *bl = mybtree_child_get(t, n, child_idx - 1);
        br = c;
        c = bl;
    }
    for (int i = 0; i < MYBTREE_KEYS_NUM_MIN; i++)
    {
        c->keys[MYBTREE_KEYS_NUM_MIN + 1 + i] = br->keys[i];
    }
    if(br->leaf) {
        for (int i = 0; i < MYBTREE_KEYS_NUM_MIN; i++)
        {
            c->data_idxs[MYBTREE_KEYS_NUM_MIN + 1 + i] = br->data_idxs[i];
            c->datas[MYBTREE_KEYS_NUM_MIN + 1 + i] = br->datas[i];
        }
    } else {
        for (int i = 0; i < MYBTREE_CHILDS_NUM_MIN; i++)
        {
            c->children_idxs[MYBTREE_CHILDS_NUM_MIN] = br->children_idxs[i];
            c->childrens[MYBTREE_KEYS_NUM_MIN + i] = br->childrens[i];
        }
    }
    c->keys[MYBTREE_KEYS_NUM_MIN] = n->keys[child_idx];
    c->keys_num += MYBTREE_KEYS_NUM_MIN + 1;
    n->keys_num--;
    if(n->keys_num = 0) {
        mybtree_node_release(t, n);
        t->root = c;
        t->root_idx = c->node_idx;
    } else {
        arr_move_left_byte(n->keys, child_idx + 1, n->keys_num - 1 - child_idx, 1, sizeof(int));
        arr_move_left_byte(n->children_idxs, child_idx + 2, n->keys_num - 1 - child_idx, 1, sizeof(int));
    }
    mybtree_node_release(t, br);
}

// 返回1表示需要子节点合并
static int mybtree_child_take(mybtree *t, mybnode *n, int i) {
    mybnode *c = mybtree_child_get(t, n, i);
    if(MYBTREE_NODE_IS_MIN(c)) {
        // 如果n的节点==t-1, 从兄弟节点借一个，或与兄弟节点合并
        mybnode *bl = mybtree_child_get(t, n, i - 1);
        if(bl && !MYBTREE_NODE_IS_MIN(bl)) {
            arr_move_right_byte(c->keys, 0, c->keys_num, 1, sizeof(int));
            c->keys[0] = bl->keys[bl->keys_num - 1];
            n->keys[i - 1] = bl->keys[bl->keys_num - 2];
            c->keys_num++;
            bl->keys_num--;
            if(!c->leaf) {
                arr_move_right_byte(c->children_idxs, 0, c->keys_num + 1, 1, sizeof(int));
                arr_move_right_byte(c->childrens, 0, c->keys_num + 1, 1, sizeof(int));
                c->children_idxs[0] = bl->children_idxs[bl->keys_num];
                c->childrens[0] = bl->childrens[bl->keys_num];
            } else {
                arr_move_right_byte(c->data_idxs, 0, c->keys_num, 1, sizeof(int));
                arr_move_right_byte(c->datas, 0, c->keys_num, 1, sizeof(int));
                c->data_idxs[0] = bl->data_idxs[bl->keys_num - 1];
                c->datas[0] = bl->datas[bl->keys_num - 1];
            }
        } else {
            mybnode *br = mybtree_child_get(t, n, i + 1);
            if(br && !MYBTREE_NODE_IS_MIN(br)) {
                c->keys[c->keys_num] = br->keys[0];
                n->keys[i] = br->keys[1];
                arr_move_left_byte(br->keys, 1, br->keys_num - 1, 1, sizeof(int));
                c->keys_num++;
                br->keys_num--;
                if(!c->leaf) {
                    arr_move_left_byte(br->children_idxs, 1, br->keys_num, 1, sizeof(int));
                    arr_move_left_byte(br->childrens, 1, br->keys_num, 1, sizeof(int));
                    c->children_idxs[c->keys_num + 1] = br->children_idxs[0];
                    c->childrens[c->keys_num + 1] = br->childrens[0];
                } else {
                    arr_move_left_byte(br->data_idxs, 1, br->keys_num - 1, 1, sizeof(int));
                    arr_move_left_byte(br->datas, 1, br->keys_num - 1, 1, sizeof(int));
                    c->data_idxs[c->keys_num] = br->data_idxs[0];
                    c->datas[c->keys_num + 1] = br->datas[0];
                }
            } else {
                return 1;
            }
        }
    }
    return 0;
}

static void mybtree_insert_nofull(mybtree *t, mybnode *n, int key, void *data) {
    if(n->leaf) {
        int i = 0;
        while (i < n->keys_num && key > n->keys[i])
        {
            i++;
        }
        for (int j = n->keys_num; j > i + 1; j--)
        {
            n->keys[j] = n->keys[j - 1];
            n->datas[j] = n->datas[j - 1];
            n->data_idxs[j] = n->data_idxs[j - 1];
        }
        n->keys[i] = key;
        n->datas[i] = data;
        n->data_idxs[i] = mybitmap_allocate(&t->bitmap_data);
        n->keys_num++;
        t->keys_num++;
        // printf("after key insert, node: %x, node size: %d, key: %d, data: %d, i: %d\n", n->node_idx, n->keys_num, key, *(int *)n->datas[i], i);
    } else {
        int i = 0;
        while (i < n->keys_num && key > n->keys[i])
        {
            i++;
        }
        mybnode *c = mybtree_child_get(t, n, i);
        if(MYBTREE_NODE_IS_FULL(c)) {
            mybtree_child_split(t, n, i);
            // printf("after split1, node: %p(%d), leaf: %d, keys: %d, %d, len: %d, childs: %d, %d, %d\n", 
            //         n, n->node_idx, n->leaf, n->keys[0], n->keys[1], n->keys_num, 
            //         n->children_idxs[0], n->children_idxs[1], n->children_idxs[2]);
            if(key > n->keys[i]) i++;
        }
        mybtree_insert_nofull(t, c, key, data);
    }
}

